#!/usr/bin/python

"""Queue - A first in first out container that allows for repositioning after insertion.
	TODO: repositioning, iterators, built ins  """

class Queue:
	"""Queue is a first in first out container. This implementation adds the ability to move the positions of the items in the queue. Defines the usual front, back, pop, and push methods."""
	def __init__(T, buffer = []):
		"""Initializes a new Queue with specified set or an empty set if none given."""
		T.buffer = buffer
	def __len__(T):
		"""Retrives the size of Queue."""
		return len(T.buffer)
	def __str__(T):
		"""String representation of object."""
		return T.__repr__()
	def __repr__(T):
		"""String representation of object."""
		tmp_str="Queue[ "
		if(T.buffer == None or len(T)==0):
			return tmp_str, "]"
		else:
			for x in T:
				tmp_str = tmp_str + "'" + str(x) + "' "
		tmp_str = tmp_str + "]"
		return tmp_str
	def __iter__(T):
		"""Allows the use of for loops for iteration through a list."""
		return Queue_Iterator(T)
	def __getitem__(T, key):
		"""Returnes item at position `key'."""
		size = len(T)
		if(size==0):
			raise EmptySetError("Cannot retrive item at %i, Queue is empty. " % key)
		if key >= size:
			raise IndexingError("Cannot retrive item at %i, Invalid key. " % key)
		return T.buffer[key]
	def __setitem__(T, key, value):
		"""Place value at location `key'."""
		size = len(T)
		if(size==0):
			raise EmptySetError("Unable to place item at %i , Queue is empty." % key)
		if key >= size:
			raise IndexingError("Cannot place item at %i, Invalid key. " % key)
		T.buffer[key]=value
	def __delitem__(T, key):
		"""Remove item at `key'."""
		size = len(T)
		if(size==0):
			raise EmptySetError("Cannot remove item %i, Queue is empty." % key)
		if key >= size:
			raise IndexingError("Cannot remove item at %i, Invalid key. " % key)
		del T.buffer[key]
	def __contains__(T,value):
		"""Returns true if value is within set."""
		return value in T.buffer
	def __getslice__(T,i,j):
		"""Returns a sub set from [i to j)."""
		size = len(T)
		if(size==0):
			raise EmptySetError("Unable to retrive items from %i to %i ; Queue is empty." % (i,j))
		if i >= size or j > size:
			raise IndexingError("Cannot retrive items at %i to %i ; Invalid keys. " % (i,j))
		return T.buffer[i:j]
	def __setslice__(T,i,j,new_set):
		"""Replace subset from [i to j] with new_set."""
		size = len(T)
		if(size==0):
			raise EmptySetError("Unable to replace items from  %i to %i; Queue is empty." % (i,j))
		if i >= size or j > size:
			raise IndexingError("Cannot retrive item from  %i to %i; Invalid keys. " % (i,j))
		T.buffer[i:j]=new_set
	def __delslice__(T,i,j):
		"""Delete subset from [i to j)."""
		size = len(T)
		if(size==0):
			raise EmptySetError("Unable to delete items from %i to %i; Queue is empty." % (i,j))
		if i >= size or j >= size:
			raise IndexingError("Cannot retrive items from %i to %i; Invalid keys. " % (i,j))
		del (T.buffer[i:j])
	def front(T):
		"""Return item at the front, next in line."""
		if(len(T)<0):
			raise EmptySetError("No front item, Queue is empty.")
		return T[0]
	def back(T):
		"""Returns item at the back, last in line."""
		if(len(T)==0):
			raise EmptySetError("No back item, Queue is empty.")
		return T[len(T)-1]
	def push(T, item):
		"""Append item on to end of Queue, add to back off line."""
		T.buffer.append(item)
	def pop(T):
		"""Retrive and remove item at front, returns and removes next in line."""
		tmp = T.front()
		T.remove(tmp)
		return tmp
	def remove(T, value):
		"""Remove `value` from queue."""
		T.buffer.remove(value)
	def swap(T,i,j):
		"""Swap items at positions `i` and `j`"""
		size = len(T)
		if(size==0):
			raise EmptySetError("Unable to swap item at %i  with item at %i, Queue is empty." % (i,j))
		if i >= size or j >= size:
			raise IndexingError("Cannot swap item at %i with item at %i, Invalid key. " % (i,j))
		tmp = T[i]
		T[i] = T[j]
		T[j] = tmp
	def move(T,i,j):
		"""Move item at position `i` to position `j`."""
		size = len(T)
		if(size==0):
			raise EmptySetError("Unable to move item from %i to %i, Queue is empty." % (i,j))
		if i >= size or j >= size:
			raise IndexingError("Cannot move item from %i to %i, Invalid key. " % (i,j))
		while i<j:
			T.swap(i,i+1)
			i+=1
		while i>j:
			T.swap(i,i-1)
			i-=1

class EmptySetError(KeyError):
	"""Raised when empty container is accessed."""
	def __init__(T, message="Container is empty."):
		"""Initialize Exception raised when empty container is accesed, pass in message or default "Container is empty." will be used."""
		T.message = message
	def __str__(T):
		"""Representation of Exception as a string."""
		return "EmptySetException: "+T.message
	def __repr__(T):
		"""Representation of Exception as a string."""
		T.__str__()

class IndexingError(KeyError):
	"""Raised when atempting to access an invalid index."""
	def __init__(T, message="Index out of bounds."):
		"""Initialize Exception raised when index is out of bounds, pass in message or default "Index out of bounds." will be used."""
		T.message = message
	def __str__(T):
		"""Representation of Exception as a string."""
		return "IndexingError: "+T.message
	def __repr__(T):
		"""Representation of Exception as a string."""
		T.__str__()


class Queue_Iterator:
	"""Iterator for Queue"""
	def __init__(T,q,i=0,j=None):
		"""Initialize iterator for Queue ranging from i to j, or the entire queue if not specified."""
		size = len(q)
		if size < 0:
			raise EmptySetError("Unable to create iterator from %i to %i, Queue is empty."%(i,j))
		if i >= size or j >= size:
			raise IndexingError("Cannot create iterator from %i to %i, invalid keys"%(i,j))
		if j==None and (not len(q)==0): 
			T.end = len(q)-1
		else: 
			T.end = j
		T.start = i
		T.buffer = q
	def next(T):
		"""Returns next item."""
		if T.start>T.end: 
			raise StopIteration()
		tmp = T.buffer[T.start]
		T.start +=1
		return tmp

